import typing
from provate import listNode, list2pList

# 题目：如果一个链表中包含环，如何找出环的入口结点

# 首先需要确定链表中是否包含环，可以使用两个指针一前一后。每次都向前走一步，如果前面得指针追上了后面的指针，那么就包含环，这时候前面指针指向得就是环的入口
# 反之，如果前面得指针走到末尾了都没有追上前面得指针，那么就不包含环

def meeting_node(head:listNode)->(listNode or None):
    if not head:
        return None

    p_1, p_2 = head, head
    for i in range(2):
        if p_1.next is not None:
            p_1 = p_1.next
        else:
            return None

    while p_1 is not None and p_1 != p_2:
        for i in range(2):
            if p_1.next is not None:
                p_1 = p_1.next
            else:
                return None

        p_2 = p_2.next

    return p_1

def entry_node_of_loop(head:listNode):
    meetingnode = meeting_node(head)
    if meetingnode is None:
        return None

    count_loop = 1

    p_node = meetingnode
    while p_node.next != meetingnode:
        p_node = p_node.next
        count_loop += 1

    p_node, p_node1 = head, head
    for i in range(count_loop):
        p_node = p_node.next

    while p_node != p_node1:
        p_node = p_node.next
        p_node1 = p_node1.next

    return p_node1

if __name__ == '__main__':
    l1 = [1,2,3,4,5,6]
    l2 = [1,2,3,4,5,6,7]
    head = list2pList(l1)
    head1 = list2pList(l2)
    p_node = head
    p_node1 = None
    while p_node.next != None:
        p_node = p_node.next
        if p_node.value == 3:
            p_node1 = p_node
    p_node.next = p_node1

    print(entry_node_of_loop(head).value)
    print(entry_node_of_loop(head1))



